#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> arr5{ "1", "101", "11001", "1111101", "1001110001", "110000110101", "11110100001001" };
    int dfs(const string& s, vector<int>& m, int i) {
        if (i == s.size()) return 0;
        if (m[i] != -1) return m[i];
        if (s[i] == '0') return INT32_MAX - 1;
        int res = INT32_MAX - 1;
        for (const auto& it : arr5) {
            if (i + it.size() > s.size()) break;
            bool flag = false;
            for (int p = i, q = 0; p < i + it.size(); ++p, ++q) {
                if (s[p] != it[q]) {
                    flag = true;
                    break;
                }
            }
            if (flag) continue;
            res = min(res, dfs(s, m, i + it.size()) + 1);
        }
        return res;
    }
    int minimumBeautifulSubstrings(string s) {
        vector<int> m(s.size(), -1);
        int ans = dfs(s, m, 0);
        if (ans == INT32_MAX - 1) ans = -1;
        return ans;
    }
};